<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3862：Little Devil I</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Little Devil I</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Little Devil I</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Little Devil I                </h1>
                <p>时间限制：8s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can&rsquo;t refuse any request from the devil. Also, this devil is looking like a very cute Loli.</div>
<div></div>
<div>The devil likes to make thing in chaos. This kingdom&rsquo;s road system is like simply a tree(connected graph without cycle). A road has a color of black or white. The devil often wants to make some change of this system.</div>
<div></div>
<div>In details, we call a path on the tree from a to b consists of vertices lie on the shortest simple path between a and b. And we say an edge is on the path if both its two endpoints is in the path, and an edge is adjacent to the path if exactly one endpoint of it is in the path.</div>
<div></div>
<div>Sometimes the devil will ask you to reverse every edge&rsquo;s color on a path or adjacent to a path.</div>
<div></div>
<div>The king&rsquo;s daughter, WJMZBMR, is also a cute loli, she is surprised by her father&rsquo;s lolicon-like behavior. As she is concerned about the road-system&rsquo;s status, sometimes she will ask you to tell there is how many black edge on a path.</div>
<div></div>
<div>Initially, every edges is white.</div>
<p></p></p><hr/><h3>输入格式</h3><p><div>The first line contains an integer T, denoting the number of the test cases.</div>
<div>For each test case, the first line contains an integer n, which is the size of the tree. The vertices be indexed from 1.</div>
<div>On the next n-1 lines, each line contains two integers a,b, denoting there is an edge between a and b.&nbsp;</div>
<div>The next line contains an integer Q, denoting the number of the operations.</div>
<div>On the next Q lines, each line contains three integers t,a,b. t=1 means we reverse every edge&rsquo;s color on path a to b. t=2 means we reverse every edge&rsquo;s color adjacent to path a to b. t=3 means we query about the number of black edge on path a to b.</div>
<div></div>
<div>T&lt;=5.</div>
<div>n,Q&lt;=10^5.</div>
<div>Please use scanf,printf instead of cin,cout,because of huge input.</div>
<p></p></p><hr/><h3>输出格式</h3><p><div>
<div>For each t=3 operation, output the answer in one line.</div>
</div>
<p></p></p><hr/><h3>样例输入</h3><pre>1
10
2 1
3 1
4 1
5 1
6 5
7 4
8 3
9 5
10 6

10
2 1 6
1 3 8
3 8 10
2 3 4
2 10 8
2 4 10
1 7 6
2 7 3
2 1 4
2 10 10
</pre><hr/><h3>样例输出</h3><pre>3</pre><hr/><h3>提示</h3><p><div>reverse color means change from white to black or vice virsa.</div>
<div></div>
<p></p></p><hr/><h3>题目来源</h3><p>By WJMZBMR</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3862" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3862" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>